package binaryTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;


/**判断二叉树是不是二叉查找树
 * */
public class JudgeBTAndBST<AnyType extends Comparable<? super AnyType>> {
	List<AnyType> list = new ArrayList<AnyType>();
	
	public boolean isBSTInOrder(BTNode<AnyType> root){
		inOrder(root);
		Iterator<AnyType> itr = list.iterator();
		AnyType pre=null;
		int flag=0;
		while(itr.hasNext()){
			AnyType data=itr.next();
			if(0==flag){
				pre=data;
				flag=1;
				continue;
			}
			//当遇到不是按照升序排序的元素时，立刻退出
			if(data.compareTo(pre)<=0){
				System.out.println("pre:"+pre+"\t"+"data:"+data);
				return false;
			}
		}
		
		return true;
	}
	
	
	public void inOrder(BTNode<AnyType> root){
		if(root!=null){
			/**遍历左子树*/
			inOrder(root.getLeftChild());
			/**访问根节点*/
			list.add((AnyType) root.getData());
			/**遍历右子树*/
			inOrder(root.getRightChild());
		}
	}
	
	
	//测试函数
	public static void main(String[] args){
		
		BinaryTree bt1=new BinaryTree();
		Scanner in=new Scanner(System.in);
		System.out.println("请输入字符串，以先序的顺序创建创建二叉树：");
		//供测试数字串 ：abd   ce  f  
		//二叉查找树:DBA  C  FE  G  
		String str=in.nextLine();
		/**将字符串转换成字符数组*/
		char[] tree=str.toCharArray();
		/**创建包装类的数组*/
		Character[] preOrder = new Character[tree.length];
		/**遍历数组，景数组中非空格的字符包装后，存入包装类数组，对空格字符赋值为null*/
		for(int i=0;i<tree.length;i++){
			if(tree[i]==' '){
				preOrder[i]=null;
			}else{
//				preOrder[i]=new Character(tree[i]);
				preOrder[i]=tree[i];
			}
		}
		/**创建二叉树*/
		bt1.setNode(((BinaryTree) bt1).createBTByPreOrder(preOrder));
		
		JudgeBTAndBST j = new JudgeBTAndBST();
		boolean result=j.isBSTInOrder(bt1.getNode());
		System.out.println("判断该二叉树是否为二叉查找树？(true/false)");
		System.out.println(result);
	}

}
